Introduction to Random Binary Search Trees

Learn how to improve efficiency of Binary Search Tree using randomization.

We'll cover the following

Here, we present a binary search tree structure that uses randomization to achieve O(logn)O(\log n) expected time for all operations.

Consider the two binary search trees shown below in figure, each of which has n=15n = 15 nodes.

Two binary search trees containing the integers 0,...,14
Two binary search trees containing the integers 0,...,14

The one on the left is a list and the other is a perfectly balanced binary search tree. The one on the left has a height of n1=14n − 1 = 14 and the one on the right has a height of three.

Imagine how these two trees could have been constructed. The one on the left occurs if we start with an empty BinarySearchTree and add the sequence

<0,1,2,3,4,5,6,7,8,9,10,11,12,13,14>\left< 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14 \right>

No other sequence of additions will create this tree (as you can prove by induction on n). On the other hand, the tree on the right can be created by the sequence

<7,3,11,1,5,9,13,0,2,4,6,8,10,12,14>\left< 7,3,11,1,5,9,13,0,2,4,6,8,10,12,14 \right>

Other sequences work as well, including

<7,3,1,5,0,2,4,6,11,9,13,8,10,12,14>\left< 7,3,1,5,0,2,4,6,11,9,13,8,10,12,14 \right>

and

<7,3,1,11,5,0,2,4,6,9,13,8,10,12,14>\left< 7,3,1,11,5,0,2,4,6,9,13,8,10,12,14 \right>

In fact, there are 21,964,80021,964,800 addition sequences that generate the tree on the right and only one that generates the tree on the left.

The above example gives some anecdotal evidence that, if we choose a random permutation of 0,...,140,...,14, and add it into a binary search tree, then we are more likely to get a very balanced tree (the right side of the above illustration, than we are to get a very unbalanced tree (the left side of the above illustration).

We can formalize this notion by studying random binary search trees. A random binary search tree of size n is obtained in the following way: Take a random permutation, x0,...,xn1x_{0},...,x_{n−1}, of the integers 0,...,n10,...,n − 1 and add its elements, one by one, into a BinarySearchTree. By random permutation we mean that each of the possible n!n! permutations (orderings) of 0,...,n10,...,n−1 is equally likely, so that the probability of obtaining any particular permutation is 1/n!1/n!.

Note that the values 0,...,n10,...,n−1 could be replaced by any ordered set of n elements without changing any of the properties of the random binary search tree. The element x{0,...,n1}x \in \{{0,...,n − 1}\} is simply standing in for the element of rank x in an ordered set of size n.

Before we can present our main result about random binary search trees, we must take some time for a short digression to discuss a type of number that comes up frequently when studying randomized structures. For a non-negative integer, kk, the kk-th harmonic number, denoted HkH_{k} , is

defined as

Hk=1+1/2+1/3++1/kH_{k} = 1 + 1/2 + 1/3 + ··· + 1/k

The harmonic number HkH_{k} has no simple closed form, but it is very closely related to the natural logarithm of k. In particular,

ln k<Hklnk+1\ln\ k < H_{k} \le \ln k + 1

Readers who have studied calculus might notice that this is because the integral 1k(1/x) dx=lnk\int_{1}^{k} (1/x) \ dx = \ln k. Keeping in mind that an integral can be interpreted as the area between a curve and the x-axis, the value of HkH_{k} can be lower-bounded by the integral 1k(1/x) dx\int_{1}^{k} (1/x) \ dx and upper-bounded by 1+1k(1/x) dx1 + \int_{1}^{k} (1/x) \ dx. See the illustration below for a graphical explanation.

Graphical representation
Graphical representation

Lemma 1: In a random binary search tree of size n, the following statements hold:

  1. For any x{0,...,n1}x \in \left\{0,...,n − 1\right\}, the expected length of the search path for xx is Hx+1+HnxO(1)H_{x+1} + H_{n−x} − O(1).

Note: The expressions x+1x+1 and nxn−x can be interpreted respectively as the number of elements in the tree less than or equal to xx and the number of elements in the tree greater than or equal to xx.

  1. For any x(1,n)\{0,...,n1}x \in (−1,n) \backslash \{0,...,n − 1\}, the expected length of the search path for xx is Hx+HnxH_{\lceil x \rceil} + H_{n-\lceil x \rceil}._

We will prove Lemma 1 in the next section. For now, consider what the two parts of Lemma 1 tell us. The first part tells us that if we search for an element in a tree of size n, then the expected length of the search path is at most 2lnn+O(1)2\ln n+O(1). The second part tells us the same thing about searching for a value not stored in the tree. When we compare the two parts of the lemma, we see that it is only slightly faster to search for something that is in the tree compared to something that is not.

Proof of Lemma 1#

The key observation needed to prove Lemma 1 is the following: The search path for a value x in the open interval (1,n)(−1,n) in a random binary search tree, T , contains the node with key i<xi < x if, and only if, in the random permutation used to create T , i appears before any of {i+1,i+2,...,x}.\{i + 1, i + 2,...,\left \lfloor x \right \rfloor\}.

To see this, refer to the below illustration.

The value i < x is on the search path for x if and only if i is that the first element among {i, i+1,...,⌊x⌋} added to the tree
The value i < x is on the search path for x if and only if i is that the first element among {i, i+1,...,⌊x⌋} added to the tree

Notice that until some value in {i,i+1,...,x}\left\{i, i + 1,...,\left \lfloor x \right \rfloor\right\} is added, the search paths for each value in the open interval (i1,x+1)(i − 1,\left \lfloor x \right \rfloor + 1) are identical. (Remember that for two values to have different search paths, there must be some element in the tree that compares differently with them.) Let j be the first element in {i,i+1,...,x}\left\{i, i+1,...,\left \lfloor x \right \rfloor\right\} to appear in the random permutation. Notice that j is now and will always be on the search path for x. If jij \ne i then the node uju_{j} containing j is created before the node uiu_{i} that contains i. Later, when i is added, it will be added to the subtree rooted at uj.leftu_{j}.\text{left}, since i<ji < j. On the other hand, the search path for x will never visit this subtree because it will proceed to uj.rightu_{j}.\text{right} after visiting uj.u_{j}.

Similarly, for i>xi > x, i appears in the search path for x if and only if i appears before any of {x,x+1,....,i1}\{\lceil x \rceil ,\lceil x \rceil + 1,....,i-1\} in the random permutation used to create T.T.

Notice that, if we start with a random permutation of {0,...,n}\{0,...,n\}, then the subsequences containing only {i,i+1,...,x}\{i, i+1,...,\lfloor x \rfloor\} and {x,x+1,...,i1}\{\lceil x \rceil, \lceil x \rceil +1,..., i-1\} are also random permutations of their respective elements. Each element, then, in the subsets {i,i+1,...,x}\{i, i+1,...,\lfloor x \rfloor\} and {x,x+1,...,i1}\{\lceil x \rceil, \lceil x \rceil +1,..., i-1\} is equally likely to appear before any other in its subset in the random permutation used to create TT . So we have

Pr{i is on the search path for x}={1/(xi+1)   if i<x1/(ix+1)   if i>x\Pr \{\text{$i$ is on the search path for $x$}\} = \begin{cases} 1/(\lfloor x \rfloor -i+1) \ \ \ \text{if $i < x$}\\ 1/(i - \lceil x \rceil +1) \ \ \ \text{if $i > x$} \end{cases}

With this observation, the proof of Lemma 1 involves some simple calculations with harmonic numbers:

Proof of Lemma 1: Let IiI_{i} be the indicator random variable that is equal to one when i appears on the search path for x and zero otherwise. Then the length of the search path is given by

i{0,...n1}\{x}Ii\sum_{i \in \{0,...n-1\} \backslash \{x\}} I_i

so, if x{0,...,n1}x \in \{0,...,n − 1\}, the expected length of the search path is given by

The probabilities of an element being on the search path for x when (a) x is an integer and (b) when x is not an integer
The probabilities of an element being on the search path for x when (a) x is an integer and (b) when x is not an integer

E[i=ox1Ii+i=x+1n1Ii]=i=ox1E[Ii]+i=x+1n1E[Ii]=i=ox11/(xi+1)+i=x+1n11/(ix+1)=i=ox11/(xi+1)+i=x+1n11/(ix+1)=12+13+...+1x+1+12+13+...+1nx=Hx+1+Hnx2.\begin{split} E \left [ \sum_{i=o}^{x-1} I_{i} + \sum_{i=x+1}^{n-1} I_{i} \right ] & = \sum_{i=o}^{x-1} E \left [ I_{i} \right ] + \sum_{i=x+1}^{n-1} E \left [ I_{i} \right ] \\ & = \sum_{i=o}^{x-1} 1/ \left ( \left \lfloor x\right \rfloor -i+1 \right ) + \sum_{i=x+1}^{n-1} 1/ \left ( i- \left \lceil x \right \rceil + 1 \right ) \\ & = \sum_{i=o}^{x-1} 1/ \left ( x -i+1 \right ) + \sum_{i=x+1}^{n-1} 1/ \left ( i- x + 1 \right ) \\ & = \frac{1}{2} + \frac{1}{3} + . . . + \frac{1}{x+1} \\ & + \frac{1}{2} + \frac{1}{3} + . . . + \frac{1}{n - x} \\ & = H_{x+1} + H_{n-x} -2 . \end{split}

The corresponding calculations for a search value x(1,n)\{0,...,n1}x \in (−1,n) \backslash \{0,...,n − 1\} are almost identical (see Figure 4.b).

Summary#

The following theorem summarizes the performance of a random binary search tree:

Theorem: A random binary search tree can be constructed in O(nlogn)O(n\log n) time. In a random binary search tree, the find(x) operation takes O(logn)O(\log n) expected time.

We should emphasize again that the expectation in theorem is with respect to the random permutation used to create the random binary search tree. In particular, it does not depend on a random choice of xx; it is true for every value of xx.

Discussion on Binary Trees

Treap: A Randomized Binary Search Tree